#!/home/zhangbing/anaconda3/bin/python
# coding=utf-8

import numpy as np
from math import *
import operator
import random
import matplotlib.pyplot as plt

label_class = ['A', 'B', 'C', 'D']
label_color = ['red', 'green', 'black', 'yellow']

#计算距离（欧拉）
def get_distance(a,b):
	A = np.array(a)
	B = np.array(b)
	C = A - B
	return sqrt(np.dot(C,np.transpose(C)))

#KNN计算
def KNN(x,label,input,k):

	m = len(x)
	result = []
	for i in range(m):#计算测试点与训练点距离
		temp = {'distance':0,'label':'A'}
		temp['distance'] = get_distance(input,x[i])
		temp['label'] = label[i]
		result.append(temp)

	sorted_result = sorted(result, key=operator.itemgetter('distance'))
	most_recent_k = sorted_result[0:k]

	statistics_label = {}
	for item in most_recent_k:
		if item['label'] not in statistics_label:
			statistics_label[item['label']] = 1
		else:
			statistics_label[item['label']] += 1

	result_label = max(zip(statistics_label.values(),statistics_label.keys()))
	return result_label[1]

#产生数据
def get_data_x():

	data_x = []
	position_center = np.array([[3,3],[12,12],[4,11],[13,2]])
	for i in range(len(label_class)):

		size = 0
		for j in range(random.randint(20,50)):
			size_random = random.randint(2,10)

			digit = 2
			uniform_x = random.uniform(position_center[i][0] - size_random, position_center[i][0] + size_random)
			position_x = round(uniform_x,digit)

			uniform_y = random.uniform(position_center[i][1] - size_random, position_center[i][1] + size_random)
			position_y = round(uniform_y,digit)

			position_random = [position_x,position_y,label_class[i]]
			data_x.append(position_random)
			size += 1

		len_data = len(data_x)
		array_x = np.array(data_x).reshape(len_data,len(data_x[0]))

		test = list(array_x[len_data - size:len_data, 0])
		show_pos_x = array_x[len_data - size:len_data, 0].astype(np.float)
		show_pos_y = array_x[len_data - size:len_data, 1].astype(np.float)

		plt.scatter(show_pos_x, show_pos_y, marker='o', color=label_color[i], s=30)

	plt.xlabel('X')  # 设置X轴标签
	plt.ylabel('Y')  # 设置Y轴标签
	plt.legend(loc='best')  # 设置 图例所在的位置 使用推荐位置
	#plt.show()
	return data_x

#获取k值
def get_k(data_x):

	random.shuffle(data_x)
	m = len(data_x)
	ratio = 0.2
	test_data_num = int(m * ratio)
	print("testing data number :" + str(test_data_num))
	testing_set = data_x[0:test_data_num]   #按比例分割数据
	training_set = data_x[test_data_num:m]

	m = len(testing_set)
	n = len(testing_set[0])
	best_k = 1
	match_sum_now = 0
	match_sum_pre = 0

	array_traning_set = np.array(training_set).reshape(len(training_set),n)

	for k in range(1, m + 1, 2): #找出最优的K值
		match_sum_now = 0
		for i in range(m):
			if KNN(array_traning_set[:,0:2].astype(np.float), array_traning_set[:,2], testing_set[i][0:n - 1], k) == testing_set[i][n - 1]:
				match_sum_now += 1
		print("k : " + str(k) + ' match : ' + str(match_sum_now))

		if match_sum_now > match_sum_pre:
			match_sum_pre = match_sum_now
			best_k = k

	return best_k

#KNN算法
def KNN_function(data,input):
	k = get_k(data_x)
	print('k = ' + str(k))
	m = len(data_x)
	n = len(data_x[0])
	array_data = np.array(data).reshape(m,n)
	return KNN(array_data[:, 0:2].astype(np.float), array_data[:, 2], input, k)


data_x = get_data_x()   #获取数据
input_pos = [12.4,1.1]  #测试点
result_label = KNN_function(data_x,input_pos) #进行KNN算法计算

plt.scatter(input_pos[0], input_pos[1], marker='o', color=label_color[label_class.index(result_label)],edgecolors='purple',s=80)#输出结果，在图上显示
plt.show()



